# -*- coding: UTF-8 -*-
print('Hello World!')

# 需要覆盖的州
states_needed = set(["mt", "wa", "or", "id", "nv", "ut", "ca", "az"])

# 广播台清单使用散列表存储
# 这里共5个广播台
stations = {}
# stations["kfive"] = set(["ca", "az"])
# stations["kthree"] = set(["or", "nv", "ca"])
# stations["kone"] = set(["id", "nv", "ut"])
# stations["kfour"] = set(["nv", "ut"])
# stations["ktwo"] = set(["wa", "id", "mt"])

stations["-1"] = set(["id", "nv", "ut"])
stations["-2"] = set(["wa", "id", "mt"])
stations["-3"] = set(["or", "nv", "ca"])
stations["-4"] = set(["nv", "ut"])
stations["-5"] = set(["ca", "az"])

# 存储最终选择的广播台
final_stations = set()

while states_needed:
    best_station = None
    # set() 转化为集合，确保集合里没有重复元素
    states_covered = set()

    # station, states 当成是一个整体看, 是stations散列表的每一项。
    # station是键, states是值。
    # 广播台及覆盖的州
    for station, states in stations.items():
        # 需要覆盖的州和该广播台覆盖的州 ，&计算交集
        covered = states_needed & states
        if len(covered) > len(states_covered):
            best_station = station
            # 一次for 循环用于寻找 覆盖needed州最多的广播台。station_needed也在不断更新
            states_covered = covered

    states_needed -= states_covered
    final_stations.add(best_station)

print(final_stations)
